The present invention relates to content addressable memories (CAM). More particularly the invention relates to a CAM architecture for reducing power consumption.
In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM""s most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not. A typical word of stored data includes actual data with a number appended header bits, such as an xe2x80x9cExe2x80x9d bit or empty bit for example, although the header bits are not specifically searched during search-and-compare operations.
A CAM stores data in a matrix of cells, which are generally either SRAM based cells or DRAM based cells. Until recently, SRAM based CAM cells have been most common because of their simple implementation. However, to provide ternary state CAMS, ie. where each CAM cell can store one of three values: a logic xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d or xe2x80x9cdon""t carexe2x80x9d result, ternary SRAM based cells typically require many more transistors than ternary DRAM based cells. As a result, ternary SRAM based CAMs have a much lower packing density than ternary DRAM based cells.
A typical CAM block diagram is shown in FIG. 1. The CAM 10 includes a matrix, or array 25, of DRAM based CAM cells (not shown) arranged in rows and columns. An array of DRAM based ternary CAM cells have the advantage of occupying significantly less silicon area than their SRAM based counterparts. A predetermined number of CAM cells in a row store a word of data. An address decoder 17 is used to select any row within the CAM array 25 to allow data to be written into or read out of the selected row. Data access circuitry such as bitlines and column selection devices, are located within the array 25 to transfer data unto and out of the array 25. Located within CAM array 25 for each row of CAM cells are matchline sense circuits, which are not shown, and are used during search and compare operations for outputting a result indicating a successful or unsuccessfully match of a search word against the stored word in the row. The results for all rows are processed by the priority encoder 22 to output the address (Match Address) corresponding to the location of a matched word. The match address is stored in match address registers 18 before being output by the match address output block 19. Data is written into array 25 through the data I/O block 11 and the various data registers 15. Data is read out from the array 25 through the data output register 23 and the data I/O block 11. Other components of the CAM include the control circuit block 12, the flag logic block 13, the voltage supply generation block 14, various control and address registers 16, refresh counter 20 and JTAG block 21.
FIG. 2 depicts a hierarchical view of the typical CAM array 25. CAM array 25 includes a matrix of CAM cells 30 and a matchline sense circuit block 26. CAM cells 30 of the CAM array 25 are arranged in rows and columns. CAM cells 30 of a row are connected to a common matchline MLi, word line WLi and tail line TLi, and CAM cells 30 of a column are connected to a common pair of search lines SLj*/SLj and a common pair of bitlines BLj/BLj*, where i is an integer value between 0 and n, and j is an integer value between 0 and m. Located adjacent to the CAM array 25 for each row is matchline sense circuit block 26. Matchline sense circuit block 26 includes one matchline sense circuit 27 connected to a respective matchline MLi, and is used during search-and-compare operations for outputting match signals ML OUTO-ML OUTn which indicate a successful or unsuccessful match of a search word against the stored word. Matchlines MLi and tail lines TLi are connected to their respective matchline sense circuits 27, and tail lines TLi can be selectively connected to ground potential. Although not shown in the simplified schematic of FIG. 2, the matchline sense circuits 27 also receive control signals to control their operation, and a person skilled in the art would understand that such control signals to be necessary for their proper operation of the circuit.
FIG. 3 shows a typical ternary DRAM type CAM cell 30 as described in issued U.S. Pat. No. 6,320,777 B1. Cell 30 has a comparison circuit which includes an n-channel search transistor 31 connected in series with a n-channel compare transistor 32 between a matchline ML and a tail line TL. A search line SL* is connected to the gate of search transistor 31. The storage current includes a n-channel access transistor 33 having a gate connected to a wordline WL and connected in series with capacitor 34 between bitline BL and a cell plate voltage potential VCP. Charge storage node CELL1 is connected to the gate of compare transistor 32 to turn on transistor 32 if there is charge stored on capacitor 34 i.e. if CELL is logic xe2x80x9cIxe2x80x9d. The remaining transistors and capacitor replicate transistors 31, 32, 33 and capacitor 34 for the other half of the ternary data bit, and are connected to corresponding lines SL and BL* and are provided to support ternary data storage. Together they can store a ternary value representing logic xe2x80x9c1xe2x80x9d, logic xe2x80x9c0xe2x80x9d, or xe2x80x9cdon""t carexe2x80x9d.
The tail line TL is typically connected to ground and all the transistors are n-channel transistors. The description of the operation of the ternary DRAM cell is detailed in the aforementioned issued patent 6,322,771 B1.
As matchlines become longer with increasing memory densities, so does the parasitic capacitance for the longer matchlines. The additional loading of the matchlines due to the increased parasitic capacitance presents several design problems associated with matchline sensing. First, the current of a single conduction path produced by a non-match CAM cell between the matchline and VSS is approximately 10 xcexcA. Hence the matchline sense amplifier must be sensitive enough to detect this small current. Second, the operating frequency of the CAM chip should be high, in other words, the working cycle of the matchline sense amplifier should be as short as possible to attain high CAM performance. Third, because all matchlines of the CAM chip are active at the same time during search-and-compare operations, the matchline voltage swing should be kept as low as possible to minimize power dissipation. Fourth, sensing should be stable and have good sensing margins for reliable sensing. Fifth, the matchline sense amplifier circuit should be simple and small enough to fit into a tight pitch CAM core layout to minimize area consumption and resulting cost. Even though the voltage swing on matchlines is kept low, power consumption still remains high due to the fully parallel searches executed by the CAM. One of the fundamental challenges for high capacity CAM""s is minimizing power consumption due to the repeated charging and discharging of match lines during search and compare operations. The power consumption of the CAM increases proportionally as the memory capacity is increases.
There are two main sources of substantial power consumption during search operations in CAM""s. Power consumed by match lines and power consumed by search lines. Conventionally, all match lines are precharged to a logic xe2x80x98Hxe2x80x99 state (a match condition), and then the comparison with search data is allowed to pull match lines to a logic xe2x80x98Lxe2x80x99 state (a must condition).
In most CAM applications xe2x80x9cmissesxe2x80x9d occur more frequently than xe2x80x9chitsxe2x80x9d. Precharging match lines to a logic xe2x80x98Hxe2x80x99 and discharging match lines to logic xe2x80x98Lxe2x80x99 for misses tends to generate high power consumption due to the high current associated with charging and discharging all match lines for each search operation. In addition, with an increased number of cells connected to each match line for wider-word CAM applications, the capacitance for match lines increases accordingly, which in turn increases the current required to charge and discharge the match lines. Various solutions have been proposed for reducing the power consumed during search operations, such as segmenting match lines into multiple segments and activating segments sequentially based on match or miss results of previous segments.
For example, a segmented match line architecture is described in U.S. Pat. No. 6,243,280 (Wong et al.)., wherein rows of the CAM are partitioned into a plurality of segments. For each match line, the first of the plurality of match line segments is precharged and a search operation is performed on the first segment. In case of a match in the first segment, the second match line segment is selectively precharged and searching proceeds to the second segment. If there is a match in the second segment, a third segment is precharged and searching proceeds in a similar manner until all segments of a match line have been searched. Precharging of a subsequent segment therefore only occurs in case of a match result in a previous segment. In the case of a match in all segments, selective precharging each segment to a logic xe2x80x98Hxe2x80x99 however still requires a large current. Furthermore, a significant delay is introduced in the search time by having to wait for the selective precharge to occur in a segment before proceeding with the actual comparison in that segment.
In U.S. Pat. No. 6,191,970 (Perena) a match line is divided into multiple segments all of which are simultaneously precharged to a logic xe2x80x98Hxe2x80x99 state prior to beginning a search operation. In addition, each CAM cell has an associated discharge circuit for selectively discharging its corresponding match line segment in response to a disable signal from a previous match line segment. A segment therefore is only discharged if the immediately preceding segment results in a miss while all subsequent segments remain precharged to a logic xe2x80x98ILxe2x80x99. As a result, the miss condition of one segment is propagated along the remainder of the row without discharging all other segments along the row. While this approach alleviates the problem of delays introduced by selectively precharging segments, the potential for high current consumption still remains, since all match lines must first be precharged to a logic xe2x80x98Hxe2x80x99 state. In addition, the match detect of each segment must be synchronized to a clock signal, clocked since the match line precharges to a hit. As a result, either a number of internal clocks must be generated, or the system clock must be used with increases system latency. Finally, in order to prevent discharge before the segment is enabled a series coupled device is added to each CAM cell, thereby increasing chip area and slowing down the entire operation.
In an article entitled xe2x80x9cUse of Selective Precharge for Low Power on the Match Lines of Content Addressable Memoriesxe2x80x9dby Zukowski et al. IEEE 19971 there is described a method whereby a small segment of an overall match line is precharged and used to perform a partial comparison first and only if a match occurs in that first small segment is the remaining segment of the match line precharged and eventually searched. The article also suggests that theoretically the selective precharge technique could be extended to cover more than one stage, but the additional overhead, extra clock phases and additional buffering would not provide any large additional gains over the single stage selective precharge proposed therein. This approach does not consider the possibility of having multiple match lien segments working sequentially but independently of clock cycles, providing a sufficient fast process technology is available to implement the necessary circuitry. Furthermore, the approach discussed by Zukowski et al. still relies on a precharge to a logic xe2x80x98Hxe2x80x99 state which can draw large amounts of current as previously explained.
Hence current CAM devices are not suitable for low power applications where conservation of battery power is critical. Thus there is still a need for CAM which is capable of consuming less power during search operations than conventional search techniques.
It is an object of the present invention to obviate or mitigate at least one disadvantage of previous CAM arrays. In particular, it is an object of the present invention to provide a content addressable memory architecture and method of operation that has reduced power consumption and that operates at high speed.
In a first aspect, the present invention provides a content addressable memory array. The content addressable memory array includes a matchline divided into a plurality of segments, where each of the plurality of segments is simultaneously precharged to a precharge voltage level in a precharge phase. The content addressable memory array also includes a matchline sense amplifier associated with each of the segments for sensing current from its associated segment in a sensing phase, where one matchline sense amplifier enables another matchline sense amplifier when a match condition is detected by the one matchline sense amplifier.
In an embodiment of the present aspect, timing circuits control precharge and sensing operations of the matchline sense amplifiers, and the timing circuits include reference matchlines in another embodiment of the present aspect, the precharge voltage level corresponds to a miss condition that corresponds to a voltage level of ground.
In yet another embodiment of the present aspect, the matchline includes a first and a second matchline segment and the matchline sense amplifier associated with the first matchline segment enables the matchline sense amplifier associated with the second matchline segment. In an aspect of the present embodiment, the first matchline segment is coupled to fewer content addressable memory cells than the second matchline segment.
In another embodiment of the present aspect, the output of each matchline sense amplifier is stored in a latch circuit.
In a second aspect, the present invention provides a method of searching a content addressable memory having a plurality of rows of CAM cells, where each row has first and second matchline segments. The method includes the steps of precharging the first and second match line segments to a potential level corresponding to a miss condition during a precharge phase, establishing a biasing potential on the first matchline segment in each row of CAM cells during a sensing phase, sensing current in the first matchline segment during the sensing phase, and selectively enabling sensing of current in the second matchline segment in each row of CAM cells if the sensed current in the first matchline segment corresponds to a match condition between the search data and the stored data.
In an embodiment of the present aspect, the step of selectively enabling sensing includes converting the sensed current into a sense node output voltage. In yet another embodiment of the present aspect, the step of selectively enabling sensing includes latching the sense node output voltage for pipelined sensing of current in the first and the second matchline segments.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.